package com.xuwei.base.algorithm;
/**
 * 约瑟芬问题，俗称丢手帕问题：
 * 有n个人围成一圈，从指定的第一个人开始从1依次报数，
 * 数到m的那个人出列，接着下一个人从1开始接着报数，
 * 直到最后只剩下一个人出列，问最后出列的是第几个人？
 * @author David
 * @since 2015年8月13日 下午4:46:16
 * @version 
 * @since JDK 1.6
 */
public class Yoseph {

	public static void main(String[] args) {
		Way1 way1=new Way1();
		way1.createLink(6);
		way1.printLink();
		way1.display(1, 3);
		
		
	}

}

/**
 * 结点类
 * @author David
 * @since 2015年8月13日 下午8:09:41
 * @version 
 * @since JDK 1.6
 */
class Node{
	private int val;
	private Node next;
	public int getVal() {
		return val;
	}
	public void setVal(int val) {
		this.val = val;
	}
	public Node getNext() {
		return next;
	}
	public void setNext(Node next) {
		this.next = next;
	}
}

/**
 * 环形链表解决约瑟夫问题
 * @author David
 * @since 2015年8月13日 下午8:10:09
 * @version 
 * @since JDK 1.6
 */
class Way1{
	private int index=1;//序号
	private Node head;//头结点
	
	public void createLink(int num){//构建链表
		head=new Node();
		head.setNext(head);
		head.setVal(1);
		Node rear=head;
		for(int i=2;i<=num;i++){
			Node p=new Node();
			p.setVal(i);;
			rear.setNext(p);
			rear=p;
			rear.setNext(head);
		}
	}
	
	public void printLink(){//打印链表
		Node p=head;
		System.out.println("约瑟夫环:");
		do{
			System.out.print(p.getVal()+"->");
			p=p.getNext();
		}while(p!=head);
		System.out.println("end");
	}
	
	/**
	 * 解约瑟夫环
	 * @param startIndex
	 * @param count
	 */
	public void display(int startIndex,int count){
		Node p=head;
		for(int i=1;i<startIndex;i++){//移动到第一个开始报数的人的位置
			p=p.getNext();
		}
		
		while(p.getNext()!=p){
			for(int j=1;j<count-1;j++){
				p=p.getNext();
			}
			delete(p);//删除p的后继结点
			p=p.getNext();
		}
		System.out.println((index++)+"---第"+head.getVal()+"个人最后出列！");
	}

	/**
	 * 删除p的后继结点
	 * @param p
	 */
	private void delete(Node p) {
		Node q=p.getNext();
		if(q==head){
			head=q.getNext();
		}
		p.setNext(q.getNext());
		System.out.println((index++)+"--- 第"+q.getVal()+"出列");
	}
}



